Reliable Delivery
Why Reliable delivery is one of the most important problems in all of the field of networking because it allows us to communicate our messages correctly to each other What ARQ Protocols Reliable delivery protocols that deal with retransmission of lost or corrupted data are known as Automatic Repeat reQuest protocols (ARQ). Additionally, the protocol needs to have these additional features in order to be useful Error Detection The receiver needs to know when a bit level error has occurred. Receiver Feedback The receiver needs to be able to communicate its positive and negative feedback back to the sender in the form of ACK and NACK packets Retransmission A packet that was received with an error must be retransmitted by the sender to the receiver How Reliable Delivery Over a Channel With Bit Errors In order to implement this, we need a flavor of ARQ protocol with an additional case in which we must handle if the ACK or NACK packet is garbled. If the feedback packet is garbled, we simply retransmit the packet. However, we may begin to introduce duplicate packets this way so we need a sequence number to keep track of which packet is being sent. Then, the receiver can check the sequence number and see if its a new transmission or a retransmission. In this way, we can avoid duplicate packets Reliable Delivery Over a Lossy Channel With Bit Errors Many communication channels are inherently lossy and so we must account for this. In order to deal with lossiness, we must answer the following two questions #How do we detect lost packets? #How do we deal with lost packets? We can answer the second question with the advances we made in solving the problem with dealing with bit errors. However, we must create a new protocol mechanism We can have the sender wait a certain amount of time for a feedback packet and if none arrive, then we can simply retransmit the packet. Since we have already solved the problem of duplicate packets, this scheme will be able to solve our lossy channel problem Pipelining Reliable Delivery Protocols Because the solutions we described above are inherently stop-and-wait protocols, the performance would be absolutely abysmal. Therefore, we need a way to pipeline both packets and feedback packets. However, because of the pipelining, we must account for several new problems that arise #We must increase the range of the sequence numbers to account for all of the packets that are currently sending #We need to buffer packets at the sender and receiver side. Minimally, we see that we must buffer packets at the sender side that have yet to receive an ACK packet Go Back N (GBN) Protocol GBN is a way to recover from pipelined delivery errors. In this protocol, we maintain a window of size N which represents how many unacknowledged packets we may have on the fly at the same time. GBN suffers from performance issues because each packet is required to be retransmitted at every small error. The GBN sender must respond to three types of events: *Invocation from above. When the application layer calls the GBN client, it should either send the packet or decline the packet if the window is already full *Receipt of an ACK. When we receive an ACK, we perform a cumulative acknowledgement. If we receive acknowledgement for packet n , then we assume that all packets up to n have also been received *A timeout event. A timer is used to recover from lost acknowledgements or corrupted packets. If the timer times out, then it resends the last N packets that were not acknowledged yet. The GBN receiver must respond to the receipt of a packet in the following ways *Valid packet. This type of packet is in order and not corrupted. We respond with an ACK for this packet *Out of order packet. This type of packet is valid (not corrupted) but it arrived out of order. We choose to discard this packet for the reasons outlined: **GBN resends all packets so we would end up with duplicate packets if we buffered packets **However, we do run into the risk of losing or having the packet be corrupted in the next time it's sent *Corrupted packet. We discard this packet. Selective Repeat (SR) Protocol SR is a more efficient protocol that deals with recovering from pipelined delivery errors. In this protocol, we also maintain a window of size N which represents how many unacknowledged packets we may have on the fly at the same time. The GBN sender must respond to three types of events: *Data received from above. When the application layer calls the SR client, it should either send the packet if there is enough room in the window or it should reject the packet if the window is full *TImeout. Each packet must have its own logical timer to deal with packet loss and corruption *ACK received. If an ACK is received, and the sequence number for that packet is the send_base number, then we move the sending window to the next unacknowledged packet with the smallest sequence number The GBN receiver must respond to the receipt of a packet in the following ways *If the packet sequence number is rcv_base, then we send a set of packets from rcv_base to the next consecutive receive numbers to the application and we move rcv_base forward by the amount of packets that were sent *Packets that have sequence number - N, rcv_base - 1 were correctly received, but an ACK must be sent anyways because otherwise, the protocol could end up being stuck on that packet *Otherwise, ignore the packet